1. Field of the Invention
The present invention relates to data busses and particularly to optimizing control flow of isochronous data on data busses.
2. Description of the Related Art
The Universal Serial Bus (USB) specification is a proposed standard for an isochronous bus recently promulgated by a group of computer companies including Compaq Computer Corporation, Digital Equipment Corporation, IBM Corporation, Intel Corporation, Microsoft Corporation and Northern Telecom. Described below are various aspects of the Universal Serial Bus. Further background concerning the Universal Serial Bus may be obtained from the Universal Serial Bus Specification, which is hereby incorporated by reference.
The Universal Serial Bus is intended as a bi-directional, isochronous, low-cost, dynamically attachable, serial interface to promote easy PC peripheral expansion and provide full support for real-time voice, audio, and compressed video data. The Universal Serial Bus provides two-wire point-to-point signaling in which the signals are differentially driven at a bit rate of 12 megabits per second. The Universal Serial Bus includes support for both isochronous and asynchronous messaging at the 12 megabit per second data speed.
The Universal Serial Bus specification defines a Universal Serial Bus system in terms of Universal Serial Bus "interconnects", "devices", and "hosts". A Universal Serial Bus interconnect defines the manner in which devices are connected to and communicate with the host, including bus topology, data flow models, scheduling, and interlayer relationships. In any given Universal Serial Bus topology, there is only one host.
Universal Serial Bus devices include hubs and functions. Hubs provide additional attachment points to the Universal Serial Bus and may be integrated with a host, which ordinarily provides only one attachment point for connecting a hub or a function. Functions provide capabilities to the system, such as joystick, keyboard, microphone, and speaker capabilities.
The basic data transfer protocol of the Universal Serial Bus is described as follows, with particular attention to FIG. 1. FIG. 1 is a diagram of the basic packet transfer 1000 of the Universal Serial Bus. The basic transfer 1000 includes a token packet 1002, a data packet 1004, and a handshake packet 1006. Each packet is preceded by a synchronization field SYNC which is used by input circuitry to align incoming data with the local clock. It is defined to be 8 bits in length and is stripped out by the connector interface.
Following the SYNC field in each packet is a packet identifier PID(T) for the token packet, PID(D) for the data packet, PID(H) for the handshake packet, and PID(S) for the start-of-frame packet, which may be considered a type of token packet). The packet identifiers PID(T), PID(D), PID(H) and PID(S) include a 4-bit identification field and a 4-bit check field used to identify the format of the packet and type. There are two types of token 1002 packet ID fields PID(T). These denote (i) a data transfer from the function to the host; and (ii) a data transfer from the host to the function. In addition to the packet ID, PID(T), the token packet includes an 8-bit address field ADDR and a 3-bit end point field, ENDP. The address field ADDR of the token packet specifies the function that it is to receive or send the data packet. The end-point field ENDP permits addressing of more than one subchannel of an individual function.
Only one type of start-of-frame packet identification field 1008, PID(S), is defined: a start of frame time stamp. The address and endpoint fields of the token packet are replaced in the start of frame packet with a time-stamp field. The time-stamp field for the start of frame packet provides a clock tick which is available to all devices on the bus. The start-of-frame packet is sent by the host every 1 ms .+-.0.01%. In addition, for both the token and start-of-frame packets, a 5-bit cyclical redundancy checksum (CRC) field is provided.
The data packet 1004 includes a packet identifier PID(D), a data field DATA, and a 16-bit cyclical redundancy checksum field, CRC16. Two types of packet IDs for the data field, data 0 and data 1, identify whether the data packet is being sent for the first time or whether being sent as a retry. The data field DATA may vary in length from 0 to N bytes. Failure of the cyclical redundancy checksum on the data field DATA causes the receiver to issue an error ERR handshake.
The handshake packet 1006 includes only a packet identifier PID(H), of which there are four types. An acknowledge handshake, ACK, indicates that the receiver will accept the data and that the CRC has succeeded. A negative acknowledge, NACK, indicates that the receiver cannot accept the data or that the source cannot send the data. An ERR field indicates that the receiver will accept the data, but that the CRC has failed. A stall handshake packet, STALL, indicates that the transmission or reception pipe is stalled. A stall handshake is defined only for stream-oriented end-points (as distinguished from message-oriented endpoints, discussed below).
Data flow on the Universal Serial Bus is defined in terms of "pipes." A pipe is a connection between a host and an endpoint. The Universal Serial Bus defines "stream" and "message" pipes. For a stream pipe, data is delivered in prenegotiated packet sizes. Data flows in at one end of the stream pipe and out the other end in the same order. Stream mode thus includes flow control and employs no defined USB structure. For a message pipe, however, a request is first sent to the device which is followed at some later time by a response from the end-point. Message pipes thus impose a structure on the data flow, which allows commands to be communicated. These commands can include band-width allocation.
The Universal Serial Bus supports isochronous, asynchronous, and asynchronous interactive data flow. For isochronous data, access to USB bandwidth is guaranteed. A constant data rate through the pipe is provided, and in the case of delivery failure due to error, there is no attempt to retry to deliver the data. Asynchronous interactive data flow provides a guaranteed service rate for the pipe, and the retry of failed transfer attempts. Asynchronous data flow accommodates access to the USB on a band-width available basis and also permits retry of data transfers.
Scheduling of the Universal Serial Bus is defined in terms of "slots", "frames" and "super frames", as illustrated in FIG. 2, which shows an exemplary USB schedule 1100. Frames 1104b and 1104a begin with a start of frame packet, 1108a and 1108b, respectively. Each frame has a duration of time equal to about 1 ms. Each frame, 1104a, 1104b is subdivided into one or more slots, 1102a, 1102b, for example. Each slot corresponds to some USB transaction, e.g., 1110a, 1110b, 11110c, 11110d. Each slot is large enough to contain the worst case transmission time of the transaction to which it corresponds, and includes the effects of bit-stuffing, propagation delay through cables and hubs, response delays, and clocking differences between the host and the end-point. A super frame 1106 consists of a repeatable sequence of individual frames, and is the largest schedulable portion of time permitted.
The Universal Serial Bus provides both periodic service and aperiodic service. For periodic service corresponding to isochronous data, a fixed period exists between the delivery of start of frame packets to a specific end-point. However, aperiodic service is characterized by a varying period between delivery of start of frame tokens for a given end-point. Periodic service is given a higher priority in scheduling than aperiodic service.
Turning now to FIG. 3, there is illustrated an abstracted block diagram of a Universal Serial Bus device, such as a hub or function. Universal Serial Bus device 1200 includes a device interface 1202 and a class interface 1204. Device interface 1202 includes device information and control block 1206, which is required for the USB device to attach to the USB and is independent of the functionality provided by the device. The device interface further includes serial bus interface engine 1210, which provide for management of the bus interface, including performing acknowledgments and recognizing packets that are addressed to the USB device. In addition, the interface engine 1210 provides for stripping the SYNC field from incoming packets. The class interface 1204 includes class information and control block 1214 which depends upon the functionality of the device (for example, hubs and locators). Class interface 1204 further includes function engine 1216 which relates to the functionality implemented by the device. A USB device further includes logical buffers, such as packet buffer 1208 and elasticity buffer 1212. The packet buffer defines the maximum packet size which the USB device can receive or send. The elasticity buffer relates to how flexible the scheduled generator may be in allocating band-width for the associated end-point and determines the maximum amount of data the device end-point can handle. The various functional blocks of the USB device are not shown connected to one another in FIG. 3 because, as discussed in the USB specification, the relationship between the components may be implementation-dependent. In addition, a Universal Serial Bus device may include storage space, local to the USB device, though addressable by the host, and vendor space, which may be defined by the vendor of the device.
While the USB is intended to be an industry-wide standard peripheral interface, the USB specification does not define the relationship between the components in a computer system employing the USB. FIG. 4 is a block diagram illustrating the configuration of the computer system employing the USB according to one embodiment of the present invention. It is noted that the configuration of FIG. 4 is for illustrative purposes only. Computer system 1400 includes a system clock 1402, a CPU 1404, a bus bridge 1406, a system memory 1408, a data producer 1410, a data producer clock 1412, a data consumer 1414, a data consumer clock 1416, a USB host 1416, a USB interface 1417, a USB function 1418, and a PCI bus 1420. System clock 1402 is a conventional clock generation circuit which is coupled to CPU 1404. CPU 1404 is a conventional central processing unit such as a microprocessor including microprocessors implementing the x86 instruction set. System memory 1408 may be any conventional data storage device such as random access memory (RAM) or read only memory (ROM). Expansion bus 1420 may be any of a variety of types of expansion busses, including a peripheral component interconnect (PCI) bus, an industry standard architecture (ISA) bus, an extended industry standard architecture (EISA) bus, or a micro-channel architecture (MCA) bus. CPU 1404, system memory 1408 and expansion bus 1420 are coupled to bus bridge 1406. Bus bridge 1406 provides an interface between CPU 1404 and system memory 1408. Additionally, bus bridge 1406 provides an interface between expansion bus 1420 and system memory 1408.
A plurality of devices may interface to expansion bus 1420. In the illustrated embodiment, data producer 1410, data consumer 1414, USB host 1416 and bus bridge 1406 interface to expansion bus 1420. Expansion bus 1420 provides an interface for the exchange of data between the devices interfaced to the bus. For example, expansion bus 1420 provides an interface for data producer 1410 to convey data to system memory 1408 via bus bridge 1406. Data producer 1410 may be any conventional device for providing input data to computer system 1400. For example, data producer 1410 may be a digital signal processor for processing input data from a modem or another bus bridge that provides data to the computer system. In the illustrated embodiment, data producer 1410 includes a data producer clock 1412. In a similar manner, data consumer 1414 may be any conventional device that receives output data from computer system 1400. For example, data consumer 1414 may be a video graphics card for outputting video data. In the illustrated embodiment, data consumer 1414 includes data consumer clock 1416.
In the illustrated embodiment, USB host 1416 interfaces to computer system 1400 via expansion bus 1420. In an alternative embodiment, USB host 1416 may be integrated into bus bridge 1406. USB host 1416 provides an interface between computer system 1400 and USB interface 1417. In the illustrated embodiment, data desired to be output on USB interface 1417 to USB function 1418 is conveyed to USB host 1416 via expansion bus 1420. USB function 1418 may be any conventional device to provide capabilities to computer system 1400, such as a joystick, a keyboard, a microphone, or a speaker. The transferred data between data producer 1410 and USB host 1416 or between USB host 1416 and data consumer 1414 is typically a two step process. Data output from data producer 1410 is first stored in system memory 1408. The data from data producer 1410 may be stored in one or more dual port first-in/first-out (FIFO) RAM arrays, or stored in a predetermined portion of the main memory. The data is then transferred from system memory 1408 to USB host 1416 via expansion bus 1420. The data received by USB host 1416 is output to USB function 1418 via USB interface 1417.
System memory 1408 functions as a buffer for storing data produced by data producer 1410. For example, the data output by data producer 1410 may be data received at a constant periodic rate while USB host 1416 outputs blocks of data at a different rate. Accordingly, system memory 1408 stores the data received from data producer 1410 so that the data is available when USB host 1416 needs a block of data. In a similar manner, data from USB host 1416 stores data in system memory 1408 and data consumer 1414 reads that data from system memory 1408.
At least three problems arise from buffering data in system memory 1408. First, the transfer of data on expansion bus 1420 creates indeterminate delays. This problem is compounded because data is transferred twice on expansion bus 1420. Second, the transfer of data between data producer 1410 and/or data consumer 1414 and USB host 1416 creates overhead on expansion bus 1420. This problem is likewise compounded by the dual transfer of data over expansion bus 1420. Lastly, buffering data in system memory 1408 increases the loading on the system memory bandwidth.
Still further, buffering data in system memory 1408 makes it complicated to adjust the data rate of the data producer 1410 or data consumer 1414 to match the data needs of USB function 1418. To prevent a buffer within system memory 1418 from overflowing, it is necessary to adjust the data output rate of data producer 1410 to closely match the rate at which USB host 1416 outputs data to USB function 1418. If the data rate of data producer 1410 exceeds the rate at which USB host 1416 is output to USB function 1418, the buffers within system memory 1408 may overflow. Similarly, if the data output rate of data producer 1410 is too slow, a block of data to transfer to USB function 1418 via USB host 1416 may not be available, which will starve USB function 1418. Accordingly, data producer clock 1412 and data consumer clock 1416 must be adjusted to substantially track the clock rate of USB function 1418. Unfortunately, the data buffers are in system memory 1418 which complicates monitoring the level of data within the buffers in order to determine and adjust the relative rates of the clocks.